package chapter16;

//*******************************************************************
//  LinkedBinaryTree.java       Java Foundations
//
//  Implements a binary tree using a linked representation.
//*******************************************************************

import chapter15.javaFoundations2nd.LinkedQueue;
import java.util.ArrayList;
import java.util.Iterator;

public class LinkedBinaryTree<T> implements BinaryTree<T>
{
    public BTNode<T> root;

    //-----------------------------------------------------------------
    //  Creates an empty binary tree.
    //-----------------------------------------------------------------
    public LinkedBinaryTree()
    {
        root = null;
    }

    //-----------------------------------------------------------------
    //  Creates a binary tree with the specified element as its root.
    //-----------------------------------------------------------------
    public LinkedBinaryTree (T element)
    {
        root = new BTNode<T>(element);
    }

    //-----------------------------------------------------------------
    //  Creates a binary tree with the two specified subtrees.
    //-----------------------------------------------------------------
    public LinkedBinaryTree (T element, LinkedBinaryTree<T> left,
                             LinkedBinaryTree<T> right)
    {
        root = new BTNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
    }

    //-----------------------------------------------------------------
    //  Returns the element stored in the root of the tree. Throws an
    //  EmptyCollectionException if the tree is empty.
    //-----------------------------------------------------------------
    public T getRootElement()throws Exception
    {
        if (root == null)
            throw new Exception ("Get root operation "
                    + "failed. The tree is empty.");

        return root.getElement();
    }

    //-----------------------------------------------------------------
    //  Returns the left subtree of the root of this tree.
    //-----------------------------------------------------------------
    public LinkedBinaryTree<T> getLeft()throws Exception
    {
        if (root == null)
            throw new Exception ("Get left operation "
                    + "failed. The tree is empty.");

        LinkedBinaryTree<T> result = new LinkedBinaryTree<T>();
        result.root = root.getLeft();

        return result;
    }

    //-----------------------------------------------------------------
    //  Returns the element in this binary tree that matches the
    //  specified target. Throws a ElementNotFoundException if the
    //  target is not found.
    //-----------------------------------------------------------------
    public T find (T target)throws Exception
    {
        BTNode<T> node = null;

        if (root != null)
            node = root.find(target);

        if (node == null)
            throw new Exception("Find operation failed. "
                    + "No such element in tree.");

        return node.getElement();
    }

    //-----------------------------------------------------------------
    //  Returns the number of elements in this binary tree.
    //-----------------------------------------------------------------
    public int size()
    {
        int result = 0;

        if (root != null)
            result = root.count();

        return result;
    }

    //-----------------------------------------------------------------
    //  Populates and returns an iterator containing the elements in
    //  this binary tree using an inorder traversal.
    //-----------------------------------------------------------------
    public ArrayList<T> inorder()
    {
        ArrayList<T> iter = new ArrayList<>();

        if (root != null)
            root.inorder (iter);

        return  iter;
    }

    //-----------------------------------------------------------------
    //  Populates and returns an iterator containing the elements in
    //  this binary tree using a levelorder traversal.
    //-----------------------------------------------------------------
    public  ArrayList<T> levelorder() throws Exception {
        LinkedQueue<BTNode<T>> queue = new LinkedQueue<BTNode<T>>();
        ArrayList<T>iter = new  ArrayList<T>();

        if (root != null)
        {
            queue.enqueue(root);
            while (!queue.isEmpty())
            {
                BTNode<T> current = queue.dequeue();

                iter.add (current.getElement());

                if (current.getLeft() != null)
                    queue.enqueue(current.getLeft());
                if (current.getRight() != null)
                    queue.enqueue(current.getRight());
            }
        }

        return iter;
    }

    //-----------------------------------------------------------------
    //  The following methods are left as programming projects.
    //-----------------------------------------------------------------
     public LinkedBinaryTree<T> getRight() throws Exception {
         if (root == null)
             throw new Exception ("Get left operation "
                     + "failed. The tree is empty.");

         LinkedBinaryTree<T> result = new LinkedBinaryTree<>();
         result.root = root.getRight();
         return result;
     }


     public boolean contains (T target) throws Exception {
        BTNode<T> node = null;
        boolean result = true;
         if (root != null)
             node = root.find(target);
        if(node == null)
            result = false;
         return result;
     }

     public boolean isEmpty() {
         boolean result = false;
         if(root == null)
             result = true;
         return result;
     }

     public String toString() {
         ArrayList<T> list = null;
         try {
             list = levelorder();
         } catch (Exception e) {
             e.printStackTrace();
         }
         String result = "";
        for(T i : list){
            result += i + "\t";
        }
        return result;
     }

     public  ArrayList<T> preorder() {
        ArrayList<T> list = new ArrayList<>();

        if(root!=null)
            root.preorder(list);
        return list;
     }

     public  ArrayList<T> postorder() {
         ArrayList<T> list = new ArrayList<>();

         if(root!=null)
             root.postorder(list);
         return list;
     }
}
